#include "Quadtree.h"

namespace binge
{

Node::Node(void)
{
    child[0] = child[1] = child[2] = child[3] = 0;
}

Node::Node(float left, float top, float right, float bottom)
{
    area.Left = left;
    area.Top = top;
    area.Right = right;
    area.Bottom = bottom;

    pushed = false;

    child[0] = child[1] = child[2] = child[3] = 0;
}

Node::~Node(void)
{
    if(child[0]) delete child[0];
    if(child[1]) delete child[1];
    if(child[2]) delete child[2];
    if(child[3]) delete child[3]; // becomes a recursive deallocation
}

void
Node::AddObject(int objId)
{
    objects.push_back(objId);
}

Quadtree::Quadtree(int levels, int width, int height)
{
    m_levels = levels;
    m_node = new Node(0, 0, width, height);

    Setup(m_node, levels);
}

Quadtree::~Quadtree(void)
{
    if(m_node != 0)
    {
        delete m_node;
    }
}

void
Quadtree::Setup(Node* node, int levels)
{
    --levels;

    if(levels >= 0)
    {
        float left = node->area.Left;
        float top = node->area.Top;
        float right = (node->area.Right-node->area.Left)/2 + left;
        float bottom = (node->area.Bottom-node->area.Top)/2 + top;
        node->child[0] = new Node(left, top, right, bottom);

        left = (node->area.Right-node->area.Left)/2 + node->area.Left;
        top = node->area.Top;
        right = (node->area.Right-node->area.Left)/2 + left;
        bottom = (node->area.Bottom-node->area.Top)/2 + top;
        node->child[1] = new Node(left, top, right, bottom);

        left = node->area.Left;
        top = (node->area.Bottom-node->area.Top)/2 + node->area.Top;
        right = (node->area.Right-node->area.Left)/2 + left;
        bottom = (node->area.Bottom-node->area.Top)/2 + top;
        node->child[2] = new Node(left, top, right, bottom);

        left = (node->area.Right-node->area.Left)/2 + node->area.Left;
        top = (node->area.Bottom-node->area.Top)/2 + node->area.Top;
        right = (node->area.Right-node->area.Left)/2 + left;
        bottom = (node->area.Bottom-node->area.Top)/2 + top;
        node->child[3] = new Node(left, top, right, bottom);

        for(int i = 0; i < 4; i++)
        {
            Setup(node->child[i], levels);  // Recursive method
        }
    }
    else
    {
        this->leafNodes.push_back(node); // its a leaf node !!
    }
}

void
Quadtree::Update(CollisionData collision)
{
    for(unsigned int i = 0; i < leafNodes.size(); i++)
    {
        leafNodes[i]->objects.clear();
        leafNodes[i]->pushed = false;
    }

    collisionNodes.clear();
    for(int i = 0; i < collision.GetCount(); i++)
    {
        int objId = collision.GetIdByIndex(i);
        UpdateNodes(m_node, objId, collision.GetRectangle(objId));
    }
}

void
Quadtree::UpdateNodes(Node* node, int objId, sf::Rect<float> colRect)
{
    if(node->child[0] != 0)
    {
        if(node->child[0]->area.Intersects(colRect))
        {
            UpdateNodes(node->child[0], objId, colRect);
        }
        if(node->child[1]->area.Intersects(colRect))
        {
            UpdateNodes(node->child[1], objId, colRect);
        }
        if(node->child[2]->area.Intersects(colRect))
        {
            UpdateNodes(node->child[2], objId, colRect);
        }
        if(node->child[3]->area.Intersects(colRect))
        {
            UpdateNodes(node->child[3], objId, colRect);
        }
    }
    else
    {
        if (node->area.Intersects(colRect))
        {
            node->AddObject(objId);
            if(!node->pushed)
            {
                collisionNodes.push_back(node); // If it has an object test it for collision
                node->pushed = true;
            }
        }
    }
}

} // namespace
